<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Map</title>
</head>

<body>
  <script>

    // Map 是一个内置对象，表示一个键值对集合。它的键可以是任何类型，包括对象、函数、基本类型等。Map 的常用方法有：set()、get()、delete()、has()、clear()、forEach() 等等。
    // 1. Map.set(key, value) 用于向 Map 中添加一个键值对。它的第一个参数是键，第二个参数是值，返回值是 Map 对象本身。
    const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]);
    myMap.set('d', 4); // Map { 'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4 }
    console.log(myMap); // Map { 'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4 }

    // 2. Map.get(key) 用于获取 Map 中某个键对应的值。它的参数是键，返回值是对应的值。
    const value = myMap.get('a'); // 1
    console.log(value); // 1

    // 3. Map.delete(key) 用于从 Map 中删除某个键值对。它的参数是键，返回值是一个布尔值，表示是否删除成功。
    myMap.delete('b'); // true
    console.log(myMap); // Map { 'a' => 1, 'c' => 3, 'd' => 4 }

    // 4. Map.has(key) 用于判断 Map 中是否包含某个键。它的参数是键，返回值是一个布尔值。
    const hasA = myMap.has('a'); // true
    const hasB = myMap.has('b'); // false
    console.log(hasA); // true
    console.log(hasB); // false

    // 5. Map.clear() 用于清空 Map。它没有参数，返回值是 Map 对象本身。
    myMap.clear(); // Map {}
    console.log(myMap); // Map {}

    // 6. Map.forEach(callbackFn, thisArg) 用于遍历 Map 中的所有键值对。它的第
    // 一个参数是回调函数，第二个参数是 this 的值（可选）。回调函数的参数是当前值、当前键、当前 Map。 
    const myMap2 = new Map([['a', 1], ['b', 2], ['c', 3]]);

    // 7. Map.size 用于获取 Map 的大小。它没有参数，返回值是一个数字，表示 Map 中键值对的个数。
    console.log(myMap2.size); // 3

    // 8. Map.entries() 用于返回一个包含 Map 中所有键值对的迭代器。它没有参数，返回值是一个迭代器对象。

    const entries = myMap2.entries();
    for (const entry of entries) {
      console.log(entry); // ['a', 1] ['b', 2] ['c', 3]
    }

    // 9. Map.keys() 用于返回一个包含 Map 中所有键的迭代器。它没有参数，返回值是一个迭代器对象。
    const keys = myMap2.keys();
    for (const key of keys) {
      console.log(key); // 'a' 'b' 'c'
    }

    // 10. Map.values() 用于返回一个包含 Map 中所有值的迭代器。它没有参数，返回值是一个迭代器对象。
    const values = myMap2.values();
    for (const value of values) {
      console.log(value); // 1 2 3
    }

    // next() 方法用于返回一个包含 Map 中下一个键值对的对象。它没有参数，返回值是一个对象，包含两个属性：value 和 done。value 是下一个键值对，done 是一个布尔值，表示是否遍历完成。
    const iterator = myMap2.entries();
    let result = iterator.next(); // { value: [ 'a', 1 ], done: false }
    console.log(result); // { value: [ 'a', 1 ], done: false }


    // 应用场景：
    // 1.实现 LRU 缓存
    class LRUCache {
      constructor(limit) {
        this.cache = new Map();
        this.limit = limit;
      }
      get(key) {
        if (!this.cache.has(key)) return null;
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value); // 更新为最近使用
        return value;
      }
      set(key, value) {
        if (this.cache.has(key)) {
          this.cache.delete(key);
        } else if (this.cache.size >= this.limit) {
          const oldestKey = this.cache.keys().next().value;
          this.cache.delete(oldestKey); // 删除最久未使用
        }
        this.cache.set(key, value);
      }
    }
    
    debugger;
    const lru = new LRUCache(2);
    lru.set('a', 1);
    lru.set('b', 2);
    lru.get('a'); // 1
    lru.set('c', 3); // 删除 'b'
    console.log([...lru.cache.keys()]); // ['a', 'c']
    console.log([...lru.cache]); // undefined
    console.log(lru.cache.keys());
    console.log(lru.cache.keys().next());

    // 数组有next属性吗？
    // 数组没有next属性，next是迭代器对象的一个方法，用于返回下一个元素。数组本身没有next方法，但可以通过Array.prototype[Symbol.iterator]()方法获取迭代器对象，然后使用next()方法遍历数组元素。 
    // 例如：
    const arr = [1, 2, 3];
    const iterator2 = arr[Symbol.iterator](); // 获取迭代器对象
    console.log(iterator2.next()); // { value: 1, done: false }


    // 2.实现双向链表
    class Node {
      constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
      }
    }

    class DoublyLinkedList {
      constructor() {
        this.head = null;
        this.tail = null;
      }
      append(key, value) {
        const newNode = new Node(key, value);
        if (!this.head) {
          this.head = newNode;
          this.tail = newNode;
        } else {
          this.tail.next = newNode;
          newNode.prev = this.tail;
          this.tail = newNode;
        }
      }
      remove(node) {
        if (node.prev) node.prev.next = node.next;
        if (node.next) node.next.prev = node.prev;
        if (node === this.head) this.head = node.next;
        if (node === this.tail) this.tail = node.prev;
      }
    }

    const list = new DoublyLinkedList();
    list.append('a', 1);
    list.append('b', 2);
    list.append('c', 3);
    console.log(list.head); // Node { key: 'a', value: 1, prev: null, next: Node { ... } }
    console.log(list.tail); // Node { key: 'c', value: 3, prev: Node { ... }, next: null }  
    console.log(list.head.next); // Node { key: 'b', value: 2, prev: Node { ... }, next: Node { ... } }
    console.log(list.tail.prev); // Node { key: 'b', value: 2, prev: Node { ... }, next: Node { ... } }
    console.log(list.head.next.prev); // Node { key: 'a', value: 1, prev: null, next: Node { ... } }


    // 3.实现图
    class Graph {
      constructor() {
        this.adjacencyList = new Map();
      }
      addVertex(vertex) {
        this.adjacencyList.set(vertex, []);
      }
      addEdge(vertex1, vertex2) {
        this.adjacencyList.get(vertex1).push(vertex2);
        this.adjacencyList.get(vertex2).push(vertex1); // 无向图
      }
      getNeighbors(vertex) {
        return this.adjacencyList.get(vertex);
      }
    }

    const graph = new Graph();
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');

    console.log(graph.adjacencyList); // Map { 'A' => [ 'B', 'C' ], 'B' => [ 'A' ], 'C' => [ 'A' ] }
    console.log(graph.getNeighbors('A')); // [ 'B', 'C' ]
    console.log(graph.getNeighbors('B')); // [ 'A' ]
    console.log(graph.getNeighbors('C')); // [ 'A' ]
    console.log(graph.getNeighbors('D')); // undefined


    // 4.实现哈希表
    class HashTable {
      constructor(size) {
        this.size = size;
        this.table = new Array(size);
      }
      hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
          hash += key.charCodeAt(i);
        }
        return hash % this.size;
      }
      set(key, value) {
        const index = this.hash(key);
        if (!this.table[index]) {
          this.table[index] = [];
        }
        this.table[index].push([key, value]);
      }
      get(key) {
        const index = this.hash(key);
        if (!this.table[index]) return null;
        for (const [k, v] of this.table[index]) {
          if (k === key) return v;
        }
        return null;
      }
    }

    const hashTable = new HashTable(10);
    hashTable.set('a', 1);
    hashTable.set('b', 2);
    hashTable.set('c', 3);


    // 5.实现队列

    // 6.实现栈

    // 7.Map实现去重
    const arr1 = [1, 2, 3, 4, 5, 1, 2, 3];
    const uniqueArr = [...new Map(arr1.map(item => [item, item])).values()];
    console.log(uniqueArr); // [1, 2, 3, 4, 5]

    // 怎么遍历 ES6 中的 Map 对象？
    // 1. forEach() 方法：可以遍历 Map 中的每个键值对。
    const map = new Map([['a', 1], ['b', 2], ['c', 3]]);
    map.forEach((value, key) => {
      console.log(key, value); // a 1 b 2 c 3
    });

    // 2. for...of 循环：可以遍历 Map 中的每个键值对。
    for (const [key, value] of map) {
      console.log(key, value); // a 1 b 2 c 3
    }

    // 3. entries() 方法：返回一个包含 Map 中所有键值对的迭代器。
    const entries2 = map.entries();
    for (const entry of entries2) {
      console.log(entry); // ['a', 1] ['b', 2] ['c', 3]
    }

    // 4. keys() 方法：返回一个包含 Map 中所有键的迭代器。
    const keys2 = map.keys();
    for (const key of keys2) {
      console.log(key); // 'a' 'b' 'c'
    }

    // 5. values() 方法：返回一个包含 Map 中所有值的迭代器。
    
    // 6. for...in 循环：不能直接遍历 Map 对象，但可以通过 Object.keys() 方法获取 Map 中的所有键，然后使用 for...in 循环遍历。
    const keys3 = Object.keys(map);
    for (const key of keys3) {
      console.log(key, map.get(key)); // a 1 b 2 c 3
    }

    // 7. Array.from() 方法：可以将 Map 对象转换为数组，然后使用 forEach() 方法遍历。

    // 8. 扩展运算符：可以将 Map 对象转换为数组，然后使用 forEach() 方法遍历。

    // 9. 迭代器：可以使用 Map 对象的迭代器方法（如 entries()、keys()、values()）获取迭代器对象，然后使用 for...of 循环遍历。

    //  

  </script>
</body>

</html>